package ink.lovejinhu.leetcode;

import ink.lovejinhu.common.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * @Author: jin
 * @Date: 2021/9/10 21:03
 * @Version: V1.0
 * @Slogan: Great people are not born great, but show their greatness in the process of growing up
 **/
public class Solution_0897 {
    public List<TreeNode> res = new ArrayList<>();

    public TreeNode increasingBST(TreeNode root) {
        this.dfs(root);
        Collections.sort(res, new Comparator<TreeNode>() {
            @Override
            public int compare(TreeNode o1, TreeNode o2) {
                return o1.val - o2.val;
            }
        });


        for (int i = 0; i < res.size() - 1; i++) {
            TreeNode treeNode = res.get(i);
            treeNode.left = null;
            treeNode.right = res.get(i + 1);
        }
        res.get(res.size() - 1).right = null;
        res.get(res.size() - 1).left = null;
        return res.get(0);
    }

    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        res.add(root);
        dfs(root.left);
        dfs(root.right);
    }
}
